package pers.vic.basics.leetcode;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;
import com.sun.org.apache.bcel.internal.generic.RETURN;

/**
 * @description: 79. 单词搜索 {@literal https://leetcode-cn.com/problems/word-search/} 回溯 注意减枝
 * @author Vic.xu
 * @date: 2021/1/15 0015 9:39
 */
public class J0079_M_Exist {
    /*
    给定一个二维网格和一个单词，找出该单词是否存在于网格中。
    单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     */

    /**
     * 回溯 注意减枝
     * 如果当前字符匹配，则在下一个单词的上下左右四个方向查找下一个字符是否匹配即可
     */
    public static boolean exist(char[][] board, String word) {
        int len = word.length();
        int row = board.length;
        int column = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (check(board, word, 0, i, j, new boolean[row][column])) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean check(char[][] board, String word, int wordIndex, int rowIndex, int columnIndex, boolean[][] used) {
        // 下标越界
        if (rowIndex < 0 || columnIndex < 0 || rowIndex >= board.length || columnIndex >= board[0].length) {
            return false;
        }
        //当前字符 是否  未被使用 且匹配
        if (used[rowIndex][columnIndex] || board[rowIndex][columnIndex] != word.charAt(wordIndex)) {
            return false;
        }
        //字符已经匹配完
        if (wordIndex == word.length() - 1) {
            return true;
        }
        //把当前位置的字符置为已使用
        used[rowIndex][columnIndex] = true;
        //校验下一个字符在下四个方向是否匹配 上 下 左 右
        boolean result = check(board, word, wordIndex + 1, rowIndex - 1, columnIndex, used)
                || check(board, word, wordIndex + 1, rowIndex + 1, columnIndex, used)
                || check(board, word, wordIndex + 1, rowIndex, columnIndex - 1, used)
                || check(board, word, wordIndex + 1, rowIndex, columnIndex + 1, used);

        //减枝
        used[rowIndex][columnIndex] = false;
        return result;
    }

    public static void main(String[] args) {
        char[][] board =
                {
                        {'A', 'B', 'C', 'E'},
                        {'S', 'F', 'C', 'S'},
                        {'A', 'D', 'E', 'E'}
                };
        System.out.println(exist(board, "ABCCED"));
        System.out.println(exist(board, "SEE"));
        System.out.println(exist(board, "ABCB"));

        char[][] board2 = {{'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a'}, {'a', 'a', 'a', 'a'}};
        System.out.println("aaaaaaaaaaaaa".length());
        System.out.println(exist(board2, "aaaaaaaaaaaaa"));
    }
}
